\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{graphicx} % para insertar imagenes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% macros para pseudocodigo %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\func}[2]{\texttt{#1}(#2)\\}
\newcommand{\tab}{\hspace*{2em}}
\newcommand{\FOR}{\textbf{for }}
\newcommand{\TO}{\textbf{ to }}
\newcommand{\IF}{\textbf{if }}
\newcommand{\INC}{\textbf{inc }}
\newcommand{\WHILE}{\textbf{while }}
\newcommand{\THEN}{\textbf{then }}
\newcommand{\ELSE}{\textbf{else }}
\newcommand{\RET}{\textbf{return }}
\newcommand{\MOD}{\textbf{ \% }}
\newcommand{\OR}{\textbf{ or }}
\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}
\newcommand{\gramed}[1]{\noindent\includegraphics[scale=0.5]{#1}\\}
\newcommand{\gra}[1]{\noindent\includegraphics[scale=0.30]{#1}}
\newcommand{\inst}[1]{\texttt{\textbf{#1}}}
\newcommand{\descrip}[1]{\textit{(#1)}}
\newenvironment{pseudo}{\vspace*{2em}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\dirmail}[1]{\normalsize{\texttt{#1}}}

\title{{\sc\normalsize Organización del computador II}\\{\bf Trabajo Práctico Nº1B}}
\author{\begin{tabular}{lcr}Thomas Fischer & 489/08 & \dirmail{tfischer@dc.uba.ar}\\Kevin Allekotte & 490/08 & \dirmail{kevinalle@gmail.com} \end{tabular}}
\date{\VSP \normalsize{Octubre 2009}}

\begin{document}

	\begin{titlepage}
		\maketitle
	\end{titlepage}

	\tableofcontents
	\newpage

	\begin{section}{Introducción}
		El objetivo de este trabajo es optimizar las funciones de detección de bordes en imágenes del \textbf{TP1A}. Para esto utilizamos el modelo de programación \texttt{SIMD} (\textit{Single Instruction Multiple Data}) y el set de instrucciones \texttt{SSE} (\textit{Streaming SIMD Extensions}) de la arquitectura IA-32 de Intel.
		
		Además implementamos un filtro nuevo: el operador de Frei-Chen, para el cual utilizamos las operaciones de punto flotante de \texttt{SSE} y un poco de ayuda de la \texttt{FPU}.
		
		Gracias a los registros \texttt{xmm} de 128 bits y las instrucciones sobre datos empaquetados que implementan podemos procesar la imagen de a 14 pixels a la vez. Esto debería hacer las funciones mucho más rápidas que las mismas implementadas con los registros \texttt{GPR} (de proposito general).
		
		Por esa razón este trabajo tiene como segundo objetivo la medición de tiempos de ejecución de los filtros y la comparación con los del trabajo anterior y los de la librería \texttt{OpenCv}.
	\end{section}

	\begin{section}{Desarrollo}
	
		\begin{subsection}{General}
			En todos los casos, el algoritmo consiste en inicializar ciertos registros contadores y punteros, recorrer la imagen original por fila, con el objetivo de minimizar los accesos a memoria y la redundancia al pedir datos, y maximizar la cantidad de píxeles que puedo calcular de la imagen destino.

			Con todos los operadores que utilizan una matriz de convolución de $3 \times 3$ (\textit{Sobel},\textit{Prewitt},\textit{Frei-chen}), recorremos desde la segunda fila hasta la anteúltima, cargando 3 líneas de 16 pixeles en 3 registros \texttt{xmm} por iteración, con los cuáles podemos calcular 14 nuevos de la imagen destino.

			Con el operador de \textit{Roberts}, que utiliza una matriz de convolución de $2 \times 2$, recorremos todas las filas menos la última, levantando 2 líneas de 16 píxeles en 2 registros por iteración, lo cuál nos permite calcular 15 nuevos de la imagen destino.

			Las líneas las recorremos avanzando de a 14 o 15 posiciones de memoria, y al final de la misma acomodamos el registro para que trabaje sobre los últimos 16 bytes de la línea, sin pasarse. Esto a veces lleva a calcular algunos píxeles de nuevo, lo cuál no es un problema porque \texttt{SSE} los calcula paralelamente a los que todavía hacen falta.

			Los datos los trabajamos, en general, empaquetados de a words, ya que necesitabamos más precisión para luego saturar el resultado de la aplicación del operador a un byte. Esto requiere que para cada iteración, desempaquetemos cada línea (registro xmm) a otros dos registros y así ganar el doble de precisión. Luego para obtener el resultado al final, hay que volver a empaquetar de word a byte con saturacion.
			\texttt{SSE} provee un set de instrucciónes para empaquetar y desempaquetar que nos fueron muy útiles.

			Para aplicar los operadores, teníamos que hacer sumas de columnas y de filas.
			La suma de columnas es bastante trivial, ya que consiste en hacer la suma empaquetada de dos registros que contienen a las líneas de píxeles correspondientes a las imágenes.
			Para la suma de columnas, tuvimos que copiar el mismo registro a otro tantas veces como columnas queríamos sumar, y luego correr todos los datos tantos lugares a la derecha como la distancia entre la columna que representaba y la original.
			Otra vez, \texttt{SSE} provee un set de instrucciones muy rico para este tipo de operaciones.

			En el caso de tener que multiplicar alguna fila o columna por algun numero, la operacion se hacía de forma empaquetada sobre el registro donde estaba representada la misma, antes de efectuarse la suma con otras filas o columnas.

			Todos los operadores (excepto \texttt{SobelX} y \texttt{SobelY}) calculan primero el operador en la dirección X, luego en Y, y luego efectúan una suma saturada de ambas.
			
			Las implementaciones de cada operador en particular no se distinguen mucho entre sí, excepto tal vez el operador de \textit{Frei-chen}.
		\end{subsection}

		\begin{subsection}{Frei-chen}
			Para aplicar el operador de \textit{Frei-chen}, previamente a iniciar el ciclo sobre la imagen, calculamos $\sqrt{2}$ en formato floating point y luego luego lo guardamos en una variable auxiliar en memoria, ya que este valor es requerido por la matriz de convolución en cuestión.

			Al tener que multiplicar una fila o columna por  $\sqrt{2}$, tuvimos transformar a la misma a formato \texttt{float} empaquetado para aplicarle operaciones como la multiplicación en un formato de punto flotante, y así no perder demasiada información.

			Esto requiere separar cada registro de words empaquetados a registros de numeros en formato \texttt{float} (32 bits) empaquetados, aplicar las operaciones de punto flotante, y volver a transformar los números a formato entero.
			
			El problema de trabajar en floating point es que cada valor (pixel) ocupa 32 bits, y para procesar los datos de a 16 pixel no nos alcanzarían los registros \texttt{xmm}. Por esto decidimos hacer todas las operaciones en enteros, pero con 4 bits de precisión adicional. Osea, cuando desempaquetamos los datos multiplicamos todo por 16. Hacemos todos los calculos con los nuevos valores y antes de reempaquetarlos los dividimos por 16.
			
			De esta forma podemos trabajar en enteros de 16 bits (de la misma forma que con los otros operadores) sin perder presición en el resultado.
		\end{subsection}
		
		\begin{subsection}{Operaciones con registros \texttt{xmm}}
			Acá hay un listado de operaciones comunes que hacemos sobre \texttt{xmm} para aplicar los operadores.
			
			\begin{subsubsection}{Desempaquetado}
				\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
				\hline a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p\\
				\hline
				\multicolumn{16}{c}{$\Downarrow$}\\
				\hline
				\multicolumn{2}{|c|}{a}&\multicolumn{2}{|c|}{b}&\multicolumn{2}{|c|}{c}&\multicolumn{2}{|c|}{d}&\multicolumn{2}{|c|}{e}&\multicolumn{2}{|c|}{f}&\multicolumn{2}{|c|}{g}&\multicolumn{2}{|c|}{h}\\
				\hline
				\hline
				\multicolumn{2}{|c|}{i}&\multicolumn{2}{|c|}{j}&\multicolumn{2}{|c|}{k}&\multicolumn{2}{|c|}{l}&\multicolumn{2}{|c|}{m}&\multicolumn{2}{|c|}{n}&\multicolumn{2}{|c|}{o}&\multicolumn{2}{|c|}{p}\\
				\hline
				\end{tabular}
				
				Usando la instrucción \inst{punpcklbw} \descrip{Unpack Low Bytes to Word} convertimos los 8 primeros bytes a words y los guardamos en otro registro, y con \inst{punpckhbw} \descrip{Unpack High Bytes to Word} hacemos lo mismo con los 8 últimos.
			\end{subsubsection}
			
			\begin{subsubsection}{Suma Vertical}
				\begin{tabular}{|c|c|c|c|c|c|c|c|}
				\hline a&b&c&d&e&f&g&h\\ \hline
				\multicolumn{8}{c}{$+$}\\
				\hline a'&b'&c'&d'&e'&f'&g'&h'\\ \hline
				\multicolumn{8}{c}{$\Downarrow$}\\
				\hline a+a'&b+b'&c+c'&d+d'&e+e'&f+f'&g+g'&h+h'\\	\hline
				\end{tabular}
				
				Esta suma se logra directamente mediante la instrucción \inst{paddw} \descrip{Packed ADD Words} que suma word a word los registros.
			\end{subsubsection}
			
			\begin{subsubsection}{Producto}
				Quiero multiplicar todos los elementos de un registro por un número.
				\begin{tabular}{|c|c|c|c|c|c|c|c|}
				\hline n&--&--&--&--&--&--&--\\ \hline
				\multicolumn{8}{c}{$\Downarrow$}\\
				\hline n&n&n&n&n&n&n&n\\ \hline
				\multicolumn{8}{c}{$\times$}\\
				\hline a&b&c&d&e&f&g&h\\ \hline
				\multicolumn{8}{c}{$\Downarrow$}\\
				\hline $n\times a$&$n\times b$&$n\times c$&$n\times d$&$n\times e$&$n\times f$&$n\times g$&$n\times h$\\ \hline
				\end{tabular}
				
				Para lograr esto primero cargamos la constante a la parte más baja de un registro y luego la copiamos a lo largo de éste con la instrucción \inst{pshufw} \descrip{Packed SHUFfle Words}. Si le pasamos el parámetro \texttt{0} (y con el mismo registro) copia el primer elemento a todos los demás.
				
				Luego el producto se hace con la instrucción \inst{pmulw}, que multiplica componente a componente 2 registros.
			\end{subsubsection}
			
			\begin{subsubsection}{Suma Horizontal}
				\begin{tabular}{|c|c|c|c|c|c|c|c|}
				\hline a&b&c&d&e&f&g&h\\ \hline
				\multicolumn{8}{c}{Quiero en cada posición la suma de los 3 vecinos}\\
				\multicolumn{8}{c}{Entonces sumo verticalmente:}\\
				\hline a&b&c&d&e&f&g&h\\ \hline
				\multicolumn{8}{c}{$+$}\\
				\hline b&c&d&e&f&g&h&0\\ \hline
				\multicolumn{8}{c}{$+$}\\
				\hline c&d&e&f&g&h&0&0\\ \hline
				\multicolumn{8}{c}{$\Downarrow$}\\
				\hline a+b+c&b+c+d&c+d+e&d+e+f&e+f+g&f+g+h&--------&--------\\ \hline
				\end{tabular}
				
				Para aplicar los operadores es muy común que haya que sumarle a cada componente el valor de sus vecinos. Para lograr esto hacemos 2 copias del registro, cada una shifteada en una posición más que la anterior y las sumamos verticalmente. El resultado es el de sumarle a cada elemento sus vecinos.
			\end{subsubsection}
			
		\end{subsection}

	\end{section}

\newpage
	%\begin{section}{Discusión}
		
	%\end{section}
	

	\begin{section}{Resultados}
		Para ver las imágenes resultantes de los algoritmos por favor ver el CD.
		
		\begin{subsection}{Tiempos de Ejecución}
			Como en el trabajo anterior, medimos los tiempos de ejecución de cada algoritmo 1000 veces, guardando los resultados promedio y mínimo de cada uno, para luego compararlos. \\% las 3 implementaciones de \texttt{Sobel}: La de la librería openCV, la de el TP anterior con registros de propósito general y la nueva con el juego de instrucciones SSE.

			\begin{tabular}{ |l|r|r| }
				\hline
								&	promedio	&	mínimo		\\
				\hline
				SobelX SSE		&	940277		&	825309		\\
				\hline
				SobelX GPR		&	11220225	&	6217315		\\
				\hline
				SobelX openCv	&	14553691	&	9787167		\\
				\hline
				Sobel SSE		&	2980943		&	1719161		\\
				\hline
				Sobel GPR		&	12885353	&	9588324		\\
				\hline
				Roberts SSE		&	1196331		&	961433		\\
				\hline
				Roberts GPR		&	15840071	&	8206330		\\
				\hline
				Prewitt SSE		&	3517818		&	1624598		\\
				\hline
				Prewitt GPR		&	17756741	&	8692477		\\
				\hline
				Frei-Chen 		&	3701883		&	2833039		\\
				\hline
			\end{tabular} \\ \\

			Como se puede apreciar en los resultados, cmparando los tiempos promedio de los operadores \textit{SobelX} vemos que nuestro algoritmo implementado con SSE es 10 veces mas rápido que el implementado en el TP1, y unas 15 veces mas rápido que el de la librería openCv.

			También vemos que el operador de roberts es notablemente mas rápido que los otros.
		\end{subsection}
	\end{section}

	\begin{section}{Conclusiones}
		El juego de instrucciones \texttt{SSE} nos permitió encarar la convolución desde una perspectiva distinta, la de trabajar con datos empaquetados. Esto mejnoro notablemente la performance de las operaciones de detección de bordes, ya que aplicar las matrices de convolución muchas veces sobre una matriz de píxeles es claramente una operación \texttt{SIMD}.
	\end{section}

	\newpage

	\begin{section}{Manual}
		\begin{subsection}{Compilación}
			Para compilar los archivos se utiliza el Makefile. Simplemente con ejecutar el comando \texttt{make} en una consola de entorno UNIX en el directorio src, se deberia generar el binario \texttt{bordes} a partir de los archivos fuente.
		\end{subsection}
		\begin{subsection}{Ejecución}
			Para usar el ejecutable se debe ejecutar \texttt{./bordes} seguido de los siguientes parámetros en el orden en que aparecen:
			\begin{enumerate}
				\item el filtro que se desea aplicar:
				\begin{itemize}
					\item \texttt{r1} (o \texttt{roberts}): operador de Roberts
					\item \texttt{r2} (o \texttt{prewitt}): operador de Prewitt
					\item \texttt{r3} (o \texttt{sobelx}): operador de Sobel en la coordenada X
					\item \texttt{r4} (o \texttt{sobely}): operador de Sobel en la coordenada Y
					\item \texttt{r5} (o \texttt{sobel}): operador de Sobel en las coordenadas XY
					\item \texttt{r6} (o \texttt{freichen}): operador de Frei-Chen
					\item \texttt{webcam}: para aplicar el filtro SobelXY a la entrada de video (webcam), o a un archivo de video (si se especifica el nombre). (Es necesario haber ejecutado \texttt{make webcam}). Los números en el teclado activan distintos filtros.
					\item \texttt{time}: mide los tiempos de ejecucion del algoritmo SobelX y los compara con el SobelX de OpenCV
				\end{itemize}
				\item La imagen de entrada (opcional): Si no es designada ninguna imagen de entrada, por defecto se aplicara el filtro sobre la imagen lena.bmp contenida en el mismo directorio
			\end{enumerate}
		\end{subsection}
	\end{section}

	\newpage

	\begin{section}{Archivos incluídos}
		\begin{itemize}
			\item src
			\begin{itemize}
				\item Makefile
				\item bordes.c
				\item webcam.c
				\item bordes.asm
				\item macros.asm
				\item sobel.asm
				\item prewitt.asm
				\item roberts.asm
				\item tp1a/Makefile
				\item tp1a/bordes.asm
				\item tp1a/macros.asm
				\item tp1a/sobel.asm
				\item tp1a/prewitt.asm
				\item tp1a/roberts.asm
			\end{itemize}
			\item exe
			\begin{itemize}
				\item bordes (bin)
			\end{itemize}
			\item enunciado
			\begin{itemize}
				\item enunciado.pdf
			\end{itemize}
			\item informe
			\begin{itemize}
				\item informe.pdf
			\end{itemize}
			\item resultados
			\begin{itemize}
				\item lena.bmp
				\item sobel\_x.bmp
				\item sobel\_y.bmp
				\item sobel.bmp
				\item prewitt.bmp
				\item roberts.bmp
				\item frei\_chen.jpg
				\item tigre.jpg
				\item tigre\_sobel.bmp
				\item tigre\_prewitt.bmp
				\item tigre\_roberts.bmp
				\item tigre\_frei\_chen.jpg
				\item eiffel.jpg
				\item eiffel\_sobel.bmp
				\item eiffel\_prewitt.bmp
				\item eiffel\_roberts.bmp
				\item eiffel\_frei\_chen.jpg
			\end{itemize}
		\end{itemize}
	\end{section}

\end{document}
